package com.sheng.leetcode.year2022.month08.day03;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/08/03
 *
 * 899. 有序队列
 *
 * 给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
 * 返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。
 *
 * 示例 1：
 * 输入：s = "cba", k = 1
 * 输出："acb"
 * 解释：
 * 在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
 * 在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
 *
 * 示例 2：
 * 输入：s = "baaca", k = 3
 * 输出："aaabc"
 * 解释：
 * 在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
 * 在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。
 *
 * 提示：
 *
 * 1 <= k <= S.length <= 1000
 * s 只由小写字母组成。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/orderly-queue
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0899 {

    @Test
    public void test01() {
        String s = "cba";
        int k = 1;
//        String s = "baaca";
//        int k = 3;
//        String s = "kuh";
//        int k = 1;
//        String s = "benb";
//        int k = 2;
        System.out.println(new Solution().orderlyQueue(s, k));
    }

}
class Solution {

    public String orderlyQueue(String s, int k) {
        int length = s.length();
        //k为2或以上时，可以交换任意两个字符之间的位置，一定会排序成字典序
        if (k == 1) {
            String result = s;
            for (int i = 0; i < length; i++) {
                s = s.substring(1, length) + s.substring(0, 1);
                result = result.compareTo(s) < 0 ? result : s;
            }
            return result;
        } else {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        }
    }
}
//class Solution {
//
//    String str;
//
//    int length;
//    public String orderlyQueue(String s, int k) {
//        str = s;
//        length = s.length();
//        if (k == 1) {
//            String result = s;
//            for (int i = 0, n = length; i < n; i++) {
//                s = s.substring(1, n) + s.substring(0, 1);
//                result = result.compareTo(s) < 0 ? result : s;
//            }
//            return result;
//        } else {
//            int judge = judge(s, k, s);
//            while (judge != -1) {
//                s = move(s, judge);
//                judge = judge(s, k, s);
//            }
//            return s;
//        }
//    }
//
//    /**
//     * 将字符串的第k个字符移动到末尾
//     *
//     * @param string 要进行移动的字符串
//     * @param k 字符串中要移动的字符的index
//     * @return 移动后的字符串
//     */
//    public String move(String string, int k) {
//        return string.substring(0, k) + string.substring(k + 1) + string.charAt(k);
//    }
//
//    /**
//     * 判断当前字符串进行移动后，在字典上是否变的更小，是则返回移动的那个位置，否则返回-1
//     *
//     * @param string 要进行移动的字符串
//     * @param k 移动的范围，前k个字符
//     * @param primaryStr 移动后进行比较的原字符串
//     * @return 需要移动的位置index
//     */
//    public int judge(String string, int k, String primaryStr) {
//        //对前k个字符进行移动后是否变的更小
//        for (int i = 0; i < k; i++) {
//            String move = move(string, i);
//            //如果在进行交换之后的字符串与最初的字符串相等，判断交换不会再产生比原字符串小的字符串，返回-1
//            if (move.equals(str)) {
//                if (string.equals(primaryStr)) {
//                    continue;
//                } else {
//                    return -1;
//                }
//            }
//            //判断移动过后的新字符串和老字符串的字典顺序
//            for (int j = 0; j < length; j++) {
//                if (primaryStr.charAt(j) > move.charAt(j)) {
//                    //字符串在进行交换之后，比原字符串的字典顺序要小，直接返回交换时用的字符串
//                    return i;
//                } else if (primaryStr.charAt(j) < move.charAt(j)) {
//                    //交换之后的字符串比原字符串还大，那么对交换过后的字符串再次进行交换，判断是否会出现比原字符串小的字符串
//                    if (judge(move, k, primaryStr) == -1) {
//                        //永远不会出现比原字符串小的字符串，返回-1
//                        break;
//                    } else {
//                        //会出现，则先按照当前i位置交换过去
//                        return i;
//                    }
//                    break;
//                }
//            }
//        }
//        return -1;
//    }
//}
